/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class LargestSumofAverages {
	double[][] res;

	public double largestSumOfAverages2(int[] A, int K) {
		res = new double[A.length][K + 1];
		help(0, K, 0.0, 0, A);
		return res[0][K];
	}

	private double help(int i, int k, double sum, int cnt, int[] a) {
		if (i < 0 || i >= a.length || k <= 0) {
			return -1;
		}
		if (i == a.length - 1) {
			if (k == 1) {
				return (sum + a[i]) / (cnt + 1);
			} else {
				return -1;
			}
		}
		if (a.length - i < k) {
			return -1;
		}
		if (res[i][k] != 0) {
			return res[i][k];
		}
		double r1 = help(i + 1, k - 1, 0, 0, a);
		double r2 = help(i + 1, k, sum + a[i], cnt + 1, a);
		if (r1 == -1 && r2 == -1) {
			res[i][k] = -1;
		} else if (r1 == -1) {
			res[i][k] = r2;
		} else if (r2 == -1) {
			res[i][k] = (sum + a[i]) / (cnt + 1) + r1;
		} else {
			res[i][k] = Math.max((sum + a[i]) / (cnt + 1) + r1, r2);
		}
		return res[i][k];
	}

	public double largestSumOfAverages(int[] A, int K) {
		int n = A.length;
		double[] sumP = new double[n + 1];
		for (int i = 0; i < n; i++) {
			sumP[i + 1] = sumP[i] + A[i];
		}
		double[][] dp = new double[n][K + 1];
		for (int i = 0; i < n; i++) {
			dp[i][1] = (sumP[n] - sumP[i]) / (n - i);
		}

		for (int k = 2; k <= K; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					dp[i][k] = Math.max(dp[i][k], (sumP[j] - sumP[i]) / (j - i) + dp[j][k - 1]);
				}
			}
		}
		return dp[0][K];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 1, 2, 3, 4, 5, 6, 7 };
		int K = 4;
		System.out.println(new LargestSumofAverages().largestSumOfAverages(A, K));
	}

}
